package com.yize.leetcode;

/**
 * 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 *
 * 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
 *
 * 示例 1:
 *
 * 输入: flowerbed = [1,0,0,0,1], n = 1
 * 输出: True
 * 示例 2:
 *
 * 输入: flowerbed = [1,0,0,0,1], n = 2
 * 输出: False
 * 注意:
 *
 * 数组内已种好的花不会违反种植规则。
 * 输入的数组长度范围为 [1, 20000]。
 * n 是非负整数，且不会超过输入数组的大小。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/can-place-flowers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class L605 {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(flowerbed.length==1){
            int x=flowerbed[0]==0?1:0;
            return x>=n;
        }
        return slove(flowerbed)>=n;
    }

    private int slove(int nums[]){
        int slow=0;//0
        int quick=0;//1
        int count=0;
        while (slow<nums.length&&quick<nums.length){
            while (slow<nums.length&&nums[slow]==1){
                slow++;
            }
            quick=slow;
            while (quick<nums.length&&nums[quick]==0){
                quick++;
            }
            if(quick-slow>=3){
                count+=counter(quick-slow);
            }
            //考虑端节点
            if((slow==0||quick==nums.length)&&(quick-slow>=2)){
                count++;
            }
            slow=quick;
        }
        return count;

    }
    //计算两个空白字符之间的
    private int counter(int sub){
        return (sub-1)/2;
    }
}
